package leetcode.pre100;

import utils.TreeNode;
import utils.TreeUtil;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉搜索树中的两个节点被错误地交换。
 * <p>
 * 请在不改变其结构的情况下，恢复这棵树。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,3,null,null,2]
 * <p>
 *    1
 *   /
 *  3
 *   \
 *    2
 * <p>
 * 输出: [3,1,null,null,2]
 * <p>
 *    3
 *   /
 *  1
 *   \
 *    2
 * 示例 2:
 * <p>
 * 输入: [3,1,4,null,null,2]
 * <p>
 * 3
 * / \
 * 1   4
 *    /
 *   2
 * <p>
 * 输出: [2,1,4,null,null,3]
 * <p>
 * 2
 * / \
 * 1   4
 *    /
 *  3
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/recover-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @since 2020/6/11 0011 下午 5:58
 */
public class Code99_recoverTree_恢复二叉搜索树 {
    public static void main(String[] args) {
        Code99_recoverTree_恢复二叉搜索树 solution = new Code99_recoverTree_恢复二叉搜索树();
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(3);
        treeNode.left.right = new TreeNode(2);
//        treeNode.right.left = new TreeNode(2);
        TreeUtil.printTree(treeNode);
        solution.recoverTree(treeNode);
        TreeUtil.printTree(treeNode);
    }

    public void recoverTree(TreeNode root) {
        if (root == null) return;
        doRecover3(root);
        swap();
    }

    /**
     * 方式1：
     * 1）中序遍历后得到一个数组，数组只有两个元素是失序的
     * 2）找到两个失序元素，标记
     * 3）中序遍历二叉树，重新赋值
     *
     * @param root
     */
    private void doRecover1(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        inOrder(root, list);
        if (list.size() == 1) return;
        if (list.size() == 2) {
            if (root.left != null) {
                root.left.val = list.get(1);
                root.val = list.get(0);
                return;
            }
            if (root.right != null) {
                root.right.val = list.get(0);
                root.val = list.get(1);
                return;
            }
        }
        //找到失序的两个位置
        int[] nums = findTarget(list);
        recover(root, nums[0], nums[1]);
    }

    //任何次序遍历都行
    private void recover(TreeNode root, int x, int y) {
        if (root == null) return;
        recover(root.left, x, y);
        if (root.val == x || root.val == y) {
            root.val =
                    root.val == x ? y : x;
        }
        recover(root.right, x, y);
    }


    private int[] findTarget(List<Integer> list) {
        // 1  2  3  4  5
        // 1  4  3  2  5
        //1)先找 list(i) > list(i+1)   i
        //2) 再找list(i) > list(i+1)   i+1

        //注意有可能交换两个相邻数字，那么只有一次满足list(i) > list(i+1)
        // 1  2  3  4  5
        // 1  3  2  4  5
        int x = 0;
        int y = 0;
        boolean first = true;
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) > list.get(i + 1)) {
                if (first) {
                    x = list.get(i);
                    first = false;
                    //只交换相邻数字的情况
                    y = list.get(i + 1);
                } else {
                    y = list.get(i + 1);
                    break;
                }
            }
        }
        return new int[]{x, y};
    }

    private void inOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }


    /**
     * 方式2：思路同方式1，只不过在遍历的过程中就找到两个交换位置
     * 空间复杂度是O(H),H为数的高度
     */
    private TreeNode x = null, y = null, pre = null;
    boolean first = true;
    public void doRecover2(TreeNode root){
        if(root == null)return;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else{
                root = stack.pop();
                //失序
                if(pre != null && root.val < pre.val){
                    if(first){
                        x = pre;
                        first = false;
                        //加这一句主要是为了防止 本身相邻的交换次序
                        y = root;
                    }else {
                        y = root;
                        //已经找到第二个，直接跳出循环
                        break;
                    }
                }
                pre = root;
                root = root.right;
            }
        }
        swap();

    }

    /**
     * 方式3：使用递归中序
     */
    public void doRecover3(TreeNode root){
        if(root == null) return;
        doRecover3(root.left);
        if(pre != null && root.val < pre.val){
            if(first){
                x = pre;
                first = false;
                y = root;
            }else {
                y = root;
                return;
            }
        }
        pre = root;
        doRecover3(root.right);
    }
    //交换找到的两个节点的值
    private void swap() {

        int temp = x.val;
        x.val = y.val;
        y.val = temp;
    }
}
